void read4punct(tim::bintree<char>& now, const char* punct)
{
	tim::stack<tim::binnode<char>*> wait;
	tim::binnode<char>* temp = NULL;
	bool isleft = false;

	for (int i = 0; punct[i] != '\0'; i++) {
		tim::binnode<char>* node = new tim::binnode<char>(punct[i]);

		switch (punct[i]) {
			case '(':
				isleft = true;
				break;
			case ',':
				isleft = false;
				if (punct[i - 1] != '(') wait.pop();
				break;
			case ')':
				isleft = false;
				wait.pop();
				break;
			default:
				if (now.is_empty())
					wait.push(now.insert_root(punct[i]));
				else if (isleft)
					wait.push(now.insert_left_child(wait.top(), punct[i]));
				else
					wait.push(now.insert_right_child(wait.top(), punct[i]));
				break;
		}
	}

	return;
}

tim::bintree<int>& huffmanEncoding(const char* code)
{
	tim::list<tim::entry<int, int>> wait;

	for (int i = 0; code[i] != '\0'; i++) {
		bool exist = false;

		for (int j = 0; j < wait.size(); j++)
			if (wait[j].value == (int)code[i]) {
				wait[j].key++;
				exist = true;
				break;
			}

		if(!exist) wait.insert_back(tim::entry<int, int>(1, (int)code[i]));
	}

	wait.sort();
	int* elems = new int[wait.size()];
	for (int i = 0; i < wait.size(); i++) elems[i] = wait[i].value;

	tim::bintree<int>* mytree = new tim::bintree<int>(elems, elems + wait.size(), true);
	return *mytree;
}

const char* huffmanDecoding(tim::bintree<int>& now, const char* code)
{
	std::string temp;
	tim::binnode<int>* temp_node = now.Root();

	for (int i = 0; code[i] != '\0'; i++) {
		if (code[i] == '0') temp_node = temp_node->left;
		else if (code[i] == '1') temp_node = temp_node->right;

		if (!temp_node->has_rchild() and !temp_node->has_lchild()) {
			temp += (char)temp_node->data;
			temp_node = now.Root();
		}
	}

	const char* temp2 = temp.c_str();
	return temp2;
}

void lab3()
{
	shower<char> myshower;
	std::string s3 = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
	std::string s4 = "A(B(D,E),C)";
	tim::bintree<char> mytree;
	read4punct(mytree, s3.c_str());
	print("Q1:");
	mytree.level_traverse<shower<char>>(myshower);
	print("\n");

	print("Q2:");
	mytree.in_traverse<shower<char>>(myshower);
	print("");
	mytree.in_traverse_re<shower<char>>(myshower);
	print("\n");

	print("Q3:");
	print(mytree.size());
	print("");

	print("Q4:");
	std::string s5 = "CASTCASTSATATATASA";
	std::string s6 = "111011001110110011001001001001100";
	tim::bintree<int> mytree2 = huffmanEncoding(s5.c_str());
	print(huffmanDecoding(mytree2, s6.c_str()));
	//mytree2.in_traverse<shower<char>>(myshower);

	return;
}


